{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "5e67dec6",
   "metadata": {},
   "source": [
    "## 2024机器智能 实验四"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "87e4f613",
   "metadata": {},
   "outputs": [],
   "source": [
    "# File: 2024机器智能实验04_teacher.ipynb\n",
    "# License: MIT License \n",
    "# Copyright: (c) 2024 Rongxi Li <lirx67@mail2.sysu.edu.cn> \n",
    "# Created: 2024-03-10\n",
    "# Brief: 2024机器智能实验课教师版——实验四"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b0362e5",
   "metadata": {},
   "source": [
    "### 必要依赖"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "0d1fb60e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Defaulting to user installation because normal site-packages is not writeable\n",
      "Requirement already satisfied: ipympl in c:\\programdata\\miniconda3\\lib\\site-packages (0.9.3)\n",
      "Requirement already satisfied: ipython<9 in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from ipympl) (8.22.1)\n",
      "Requirement already satisfied: numpy in c:\\programdata\\miniconda3\\lib\\site-packages (from ipympl) (1.26.4)\n",
      "Requirement already satisfied: ipython-genutils in c:\\programdata\\miniconda3\\lib\\site-packages (from ipympl) (0.2.0)\n",
      "Requirement already satisfied: pillow in c:\\programdata\\miniconda3\\lib\\site-packages (from ipympl) (10.2.0)\n",
      "Requirement already satisfied: traitlets<6 in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from ipympl) (5.14.1)\n",
      "Requirement already satisfied: ipywidgets<9,>=7.6.0 in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from ipympl) (8.1.2)\n",
      "Requirement already satisfied: matplotlib<4,>=3.4.0 in c:\\programdata\\miniconda3\\lib\\site-packages (from ipympl) (3.8.3)\n",
      "Requirement already satisfied: decorator in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from ipython<9->ipympl) (5.1.1)\n",
      "Requirement already satisfied: jedi>=0.16 in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from ipython<9->ipympl) (0.19.1)\n",
      "Requirement already satisfied: matplotlib-inline in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from ipython<9->ipympl) (0.1.6)\n",
      "Requirement already satisfied: prompt-toolkit<3.1.0,>=3.0.41 in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from ipython<9->ipympl) (3.0.43)\n",
      "Requirement already satisfied: pygments>=2.4.0 in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from ipython<9->ipympl) (2.17.2)\n",
      "Requirement already satisfied: stack-data in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from ipython<9->ipympl) (0.6.3)\n",
      "Requirement already satisfied: colorama in c:\\programdata\\miniconda3\\lib\\site-packages (from ipython<9->ipympl) (0.4.4)\n",
      "Requirement already satisfied: comm>=0.1.3 in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from ipywidgets<9,>=7.6.0->ipympl) (0.2.1)\n",
      "Requirement already satisfied: widgetsnbextension~=4.0.10 in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from ipywidgets<9,>=7.6.0->ipympl) (4.0.10)\n",
      "Requirement already satisfied: jupyterlab-widgets~=3.0.10 in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from ipywidgets<9,>=7.6.0->ipympl) (3.0.10)\n",
      "Requirement already satisfied: contourpy>=1.0.1 in c:\\programdata\\miniconda3\\lib\\site-packages (from matplotlib<4,>=3.4.0->ipympl) (1.2.0)\n",
      "Requirement already satisfied: cycler>=0.10 in c:\\programdata\\miniconda3\\lib\\site-packages (from matplotlib<4,>=3.4.0->ipympl) (0.12.1)\n",
      "Requirement already satisfied: fonttools>=4.22.0 in c:\\programdata\\miniconda3\\lib\\site-packages (from matplotlib<4,>=3.4.0->ipympl) (4.49.0)\n",
      "Requirement already satisfied: kiwisolver>=1.3.1 in c:\\programdata\\miniconda3\\lib\\site-packages (from matplotlib<4,>=3.4.0->ipympl) (1.4.5)\n",
      "Requirement already satisfied: packaging>=20.0 in c:\\programdata\\miniconda3\\lib\\site-packages (from matplotlib<4,>=3.4.0->ipympl) (23.0)\n",
      "Requirement already satisfied: pyparsing>=2.3.1 in c:\\programdata\\miniconda3\\lib\\site-packages (from matplotlib<4,>=3.4.0->ipympl) (3.1.1)\n",
      "Requirement already satisfied: python-dateutil>=2.7 in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from matplotlib<4,>=3.4.0->ipympl) (2.8.2)\n",
      "Requirement already satisfied: parso<0.9.0,>=0.8.3 in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from jedi>=0.16->ipython<9->ipympl) (0.8.3)\n",
      "Requirement already satisfied: wcwidth in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from prompt-toolkit<3.1.0,>=3.0.41->ipython<9->ipympl) (0.2.13)\n",
      "Requirement already satisfied: six>=1.5 in c:\\programdata\\miniconda3\\lib\\site-packages (from python-dateutil>=2.7->matplotlib<4,>=3.4.0->ipympl) (1.16.0)\n",
      "Requirement already satisfied: executing>=1.2.0 in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from stack-data->ipython<9->ipympl) (2.0.1)\n",
      "Requirement already satisfied: asttokens>=2.1.0 in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from stack-data->ipython<9->ipympl) (2.4.1)\n",
      "Requirement already satisfied: pure-eval in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from stack-data->ipython<9->ipympl) (0.2.2)\n",
      "Defaulting to user installation because normal site-packages is not writeable\n",
      "Requirement already satisfied: numpy in c:\\programdata\\miniconda3\\lib\\site-packages (1.26.4)\n",
      "Defaulting to user installation because normal site-packages is not writeable\n",
      "Requirement already satisfied: matplotlib in c:\\programdata\\miniconda3\\lib\\site-packages (3.8.3)\n",
      "Requirement already satisfied: contourpy>=1.0.1 in c:\\programdata\\miniconda3\\lib\\site-packages (from matplotlib) (1.2.0)\n",
      "Requirement already satisfied: cycler>=0.10 in c:\\programdata\\miniconda3\\lib\\site-packages (from matplotlib) (0.12.1)\n",
      "Requirement already satisfied: fonttools>=4.22.0 in c:\\programdata\\miniconda3\\lib\\site-packages (from matplotlib) (4.49.0)\n",
      "Requirement already satisfied: kiwisolver>=1.3.1 in c:\\programdata\\miniconda3\\lib\\site-packages (from matplotlib) (1.4.5)\n",
      "Requirement already satisfied: numpy<2,>=1.21 in c:\\programdata\\miniconda3\\lib\\site-packages (from matplotlib) (1.26.4)\n",
      "Requirement already satisfied: packaging>=20.0 in c:\\programdata\\miniconda3\\lib\\site-packages (from matplotlib) (23.0)\n",
      "Requirement already satisfied: pillow>=8 in c:\\programdata\\miniconda3\\lib\\site-packages (from matplotlib) (10.2.0)\n",
      "Requirement already satisfied: pyparsing>=2.3.1 in c:\\programdata\\miniconda3\\lib\\site-packages (from matplotlib) (3.1.1)\n",
      "Requirement already satisfied: python-dateutil>=2.7 in c:\\users\\jungh\\appdata\\roaming\\python\\python311\\site-packages (from matplotlib) (2.8.2)\n",
      "Requirement already satisfied: six>=1.5 in c:\\programdata\\miniconda3\\lib\\site-packages (from python-dateutil>=2.7->matplotlib) (1.16.0)\n"
     ]
    }
   ],
   "source": [
    "!pip install --upgrade ipympl\n",
    "!pip install numpy \n",
    "!pip install matplotlib"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "7e77ce06",
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib ipympl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "09f63ec1-fbd8-4e87-91b2-c3454558e91b",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.animation as animation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0fe23565",
   "metadata": {},
   "source": [
    "### PSO"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f1f32f31",
   "metadata": {},
   "source": [
    "画图函数，不用看"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "c9f883dc",
   "metadata": {},
   "outputs": [],
   "source": [
    "class PlotPSO2D:\n",
    "    def __call__(self, pop_list, decode, get_fitn, num=None):\n",
    "        boundary = decode(np.array([[0, 0], [1, 1]]))\n",
    "        x = np.linspace(boundary[0][0], boundary[1][0], 100)\n",
    "        y = np.linspace(boundary[0][1], boundary[1][1], 100)\n",
    "        X, Y = np.meshgrid(x, y)\n",
    "        Z = get_fitn(np.array([X.ravel(), Y.ravel()]).T).reshape(X.shape)\n",
    "\n",
    "        self.fig, self.ax = plt.subplots(num=num)\n",
    "        self.ax.cla()\n",
    "\n",
    "        def _update(frame):\n",
    "            idx = frame % len(pop_list)\n",
    "            pop = pop_list[idx]\n",
    "            pop = decode(pop)\n",
    "            self.ax.cla()\n",
    "            self.ax.contourf(X, Y, Z, 10, cmap=\"Greys\", alpha=0.2)\n",
    "            C = self.ax.contour(X, Y, Z, 10, alpha=1, cmap=\"YlGnBu\")\n",
    "            self.ax.clabel(C, inline=True, fontsize=10)\n",
    "\n",
    "            self.ax.set_xlim(boundary[0][0], boundary[1][0])\n",
    "            self.ax.set_ylim(boundary[0][1], boundary[1][1])\n",
    "            self.ax.scatter(pop[:, 0], pop[:, 1], c=\"r\", s=10)\n",
    "\n",
    "            self.ax.set_xlabel(\"x\")\n",
    "            self.ax.set_ylabel(\"y\")\n",
    "            self.ax.set_title(\"PSO\")\n",
    "\n",
    "        self.ani = animation.FuncAnimation(\n",
    "            self.fig, _update, frames=len(pop_list), interval=100, repeat=False\n",
    "        )\n",
    "        plt.show(self.ani)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36d9d761",
   "metadata": {},
   "source": [
    "#### 4.1 请完成PSO算法\n",
    "\n",
    "包括获取个体最优、获取全局最优、获取速度三个功能以及PSO的主要流程。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d82163b2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_pbest(pop, fit, pbest, pbest_fit):\n",
    "    \"\"\"获取个体最优\n",
    "\n",
    "    Args:\n",
    "        pop (numpy.ndarray): 粒子群，二维数组，[pn, dim]\n",
    "        fit (numpy.ndarray): 适应度，一维数组，[pn]\n",
    "        pbest (numpy.ndarray): 上一次迭代的个体最优，二维数组，[pn, dim]\n",
    "        pbest_fit (numpy.ndarray): 上一次迭代的个体最优适应度，一维数组，[pn]\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 个体最优，二维数组，[pn, dim]\n",
    "        numpy.ndarray: 个体最优适应度，一维数组，[pn]\n",
    "    \"\"\"\n",
    "    # TODO 更新个体最优\n",
    "    return pbest, pbest_fit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "8e4faef1",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 答案\n",
    "def get_pbest(pop, fit, pbest, pbest_fit):\n",
    "    \"\"\"获取个体最优\n",
    "\n",
    "    Args:\n",
    "        pop (numpy.ndarray): 粒子群，二维数组，[pn, dim]\n",
    "        fit (numpy.ndarray): 适应度，一维数组，[pn]\n",
    "        pbest (numpy.ndarray): 上一次迭代的个体最优，二维数组，[pn, dim]\n",
    "        pbest_fit (numpy.ndarray): 上一次迭代的个体最优适应度，一维数组，[pn]\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 个体最优，二维数组，[pn, dim]\n",
    "        numpy.ndarray: 个体最优适应度，一维数组，[pn]\n",
    "    \"\"\"\n",
    "    update = fit < pbest_fit\n",
    "    pbest[update] = pop[update]\n",
    "    pbest_fit[update] = fit[update]\n",
    "    return pbest, pbest_fit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "2d117383",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_gbest(pop, fit, gbest, gbest_fit):\n",
    "    \"\"\"获取全局最优\n",
    "\n",
    "    Args:\n",
    "        pop (numpy.ndarray): 粒子群，二维数组，[pn, dim]\n",
    "        fit (numpy.ndarray): 适应度，一维数组，[pn]\n",
    "        gbest (numpy.ndarray): 上一次迭代的全局最优，一维数组，[dim]\n",
    "        gbest_fit (float): 上一次迭代的全局最优适应度\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 全局最优，一维数组，[dim]\n",
    "        float: 全局最优适应度\n",
    "    \"\"\"\n",
    "    # TODO 更新全局最优\n",
    "    return gbest, gbest_fit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "49d775fb",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 答案\n",
    "def get_gbest(pop, fit, gbest, gbest_fit):\n",
    "    \"\"\"获取全局最优\n",
    "\n",
    "    Args:\n",
    "        pop (numpy.ndarray): 粒子群，二维数组，[pn, dim]\n",
    "        fit (numpy.ndarray): 适应度，一维数组，[pn]\n",
    "        gbest (numpy.ndarray): 上一次迭代的全局最优，一维数组，[dim]\n",
    "        gbest_fit (float): 上一次迭代的全局最优适应度\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 全局最优，一维数组，[dim]\n",
    "        float: 全局最优适应度\n",
    "    \"\"\"\n",
    "    idx = np.argmin(fit)\n",
    "    if fit[idx] < gbest_fit:\n",
    "        gbest = pop[idx]\n",
    "        gbest_fit = fit[idx]\n",
    "    return gbest, gbest_fit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "465a6037",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_velocity(pop, velocity, pbest, gbest, omega, c1, c2):\n",
    "    \"\"\"获取速度\n",
    "\n",
    "    Args:\n",
    "        pop (numpy.ndarray): 粒子群，二维数组，[pn, dim]\n",
    "        velocity (numpy.ndarray): 上此次迭代的速度，二维数组，[pn, dim]\n",
    "        pbest (numpy.ndarray): 个体最优，二维数组，[pn, dim]\n",
    "        gbest (numpy.ndarray): 全局最优，一维数组，[dim]\n",
    "        omega (float): 惯性权重\n",
    "        c1 (float): 局部加速系数\n",
    "        c2 (flaot): 全局加速系数\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 速度，二维数组，[pn, dim]\n",
    "    \"\"\"\n",
    "    # TODO 更新速度\n",
    "    return velocity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "dd1968e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 答案\n",
    "def get_velocity(pop, velocity, pbest, gbest, omega, c1, c2):\n",
    "    \"\"\"获取速度\n",
    "\n",
    "    Args:\n",
    "        pop (numpy.ndarray): 粒子群，二维数组，[pn, dim]\n",
    "        velocity (numpy.ndarray): 上此次迭代的速度，二维数组，[pn, dim]\n",
    "        pbest (numpy.ndarray): 个体最优，二维数组，[pn, dim]\n",
    "        gbest (numpy.ndarray): 全局最优，一维数组，[dim]\n",
    "        omega (float): 惯性权重\n",
    "        c1 (float): 局部加速系数\n",
    "        c2 (flaot): 全局加速系数\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 速度，二维数组，[pn, dim]\n",
    "    \"\"\"\n",
    "    velocity = (\n",
    "        omega * velocity\n",
    "        + c1 * np.random.rand() * (pbest - pop)\n",
    "        + c2 * np.random.rand() * (gbest - pop)\n",
    "    )\n",
    "    return velocity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "1263803f",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "<>:12: SyntaxWarning: assertion is always true, perhaps remove parentheses?\n",
      "<>:23: SyntaxWarning: assertion is always true, perhaps remove parentheses?\n",
      "<>:12: SyntaxWarning: assertion is always true, perhaps remove parentheses?\n",
      "<>:23: SyntaxWarning: assertion is always true, perhaps remove parentheses?\n",
      "C:\\Users\\jungh\\AppData\\Local\\Temp\\ipykernel_29664\\4251106477.py:12: SyntaxWarning: assertion is always true, perhaps remove parentheses?\n",
      "  assert (len(boundary.shape) in [1, 2], \"boundary shape error\")\n",
      "C:\\Users\\jungh\\AppData\\Local\\Temp\\ipykernel_29664\\4251106477.py:23: SyntaxWarning: assertion is always true, perhaps remove parentheses?\n",
      "  assert (len(data.shape) in [1, 2], \"data shape error\")\n"
     ]
    }
   ],
   "source": [
    "def get_decoder(boundary):\n",
    "    \"\"\"获取解码函数\n",
    "\n",
    "    Args:\n",
    "        boundary (numpy.ndarray): 各维度的边界。\n",
    "                二维数组，[dim, 2]，\n",
    "                当输入一维数组时将自动扩展，此时各维度的边界相同。\n",
    "\n",
    "    Returns:\n",
    "        FunctionType: 解码函数\n",
    "    \"\"\"\n",
    "    assert (len(boundary.shape) in [1, 2], \"boundary shape error\")\n",
    "\n",
    "    def _inner(data):\n",
    "        \"\"\"解码函数\n",
    "\n",
    "        Args:\n",
    "            data (numpy.ndarray): 待解码数据，二维数组，[pn, dim]\n",
    "\n",
    "        Returns:\n",
    "            numpy.ndarray: 解码后数据，二维数组，[pn, dim]\n",
    "        \"\"\"\n",
    "        assert (len(data.shape) in [1, 2], \"data shape error\")\n",
    "        nonlocal boundary\n",
    "        if len(boundary.shape) == 1:\n",
    "            boundary = np.repeat(\n",
    "                np.expand_dims(boundary, 0), repeats=data.shape[1], axis=0\n",
    "            )\n",
    "        ret = np.expand_dims(boundary[:, 0], axis=-1) + data.transpose(\n",
    "            1, 0\n",
    "        ) * np.expand_dims(boundary[:, 1] - boundary[:, 0], axis=-1)\n",
    "        return ret.transpose(1, 0)\n",
    "\n",
    "    return _inner"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "f8265c01",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_fitn_demo(pop):\n",
    "    \"\"\"获取适应度\n",
    "\n",
    "    Args:\n",
    "        pop (numpy.ndarray): 粒子群，二维数组，[pn, dim]\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 适应度，一维数组，[pn]\n",
    "    \"\"\"\n",
    "    x = pop[:, 0]\n",
    "    y = pop[:, 1]\n",
    "    return np.sin(np.sqrt(x**2 + y**2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "0703885f-d317-47dc-85a7-9241fe088ef5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def pso(pn, dim, omega, c1, c2, max_iter, decode, get_fitn):\n",
    "    \"\"\"粒子群优化\n",
    "\n",
    "    Args:\n",
    "        pn (int): 粒子数量\n",
    "        dim (int): 粒子维度\n",
    "        omega (float): 惯性权重\n",
    "        c1 (float): 局部加速系数\n",
    "        c2 (float): 全局加速系数\n",
    "        max_iter (int): 最大迭代次数\n",
    "        decode (FunctionType): 解码函数\n",
    "        get_fitn (FunctionType): 适应度函数\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 全局最优，一维数组，[dim]\n",
    "        float: 全局最优适应度\n",
    "        List: 粒子群迭代过程\n",
    "    \"\"\"\n",
    "    # 初始化粒子，速度，局部最优，全局最优等\n",
    "    pop = np.random.rand(pn, dim)\n",
    "    pop_list = [pop.copy()]\n",
    "    gbest = None # 请修改\n",
    "    gbest_fit = None # 请修改\n",
    "    # ...\n",
    "\n",
    "    for iter in range(max_iter):\n",
    "        # 计算适应度\n",
    "        # ...\n",
    "        # 计算局部最优，全局最优\n",
    "        # ...\n",
    "        # 计算速度并更新粒子位置\n",
    "        # ...\n",
    "        pop_list.append(pop.copy())\n",
    "\n",
    "    return gbest, gbest_fit, pop_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "82a76b39",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 答案\n",
    "def pso(pn, dim, omega, c1, c2, max_iter, decode, get_fitn):\n",
    "    \"\"\"粒子群优化\n",
    "\n",
    "    Args:\n",
    "        pn (int): 粒子数量\n",
    "        dim (int): 粒子维度\n",
    "        omega (float): 惯性权重\n",
    "        c1 (float): 局部加速系数\n",
    "        c2 (float): 全局加速系数\n",
    "        max_iter (int): 最大迭代次数\n",
    "        decode (FunctionType): 解码函数\n",
    "        get_fitn (FunctionType): 适应度函数\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 全局最优，一维数组，[dim]\n",
    "        float: 全局最优适应度\n",
    "        List: 粒子群迭代过程\n",
    "    \"\"\"\n",
    "    pop = np.random.rand(pn, dim)\n",
    "    pbest = pop\n",
    "    pbest_fit = get_fitn(decode(pop))\n",
    "    gbest = pbest[np.argmin(pbest_fit)]\n",
    "    gbest_fit = np.max(pbest_fit)\n",
    "    velocity = np.zeros((pn, dim))\n",
    "    pop_list = [pop.copy()]\n",
    "\n",
    "    for iter in range(max_iter):\n",
    "        fitness = get_fitn(decode(pop))\n",
    "        pbest, pbest_fit = get_pbest(pop, fitness, pbest, pbest_fit)\n",
    "        gbest, gbest_fit = get_gbest(pop, fitness, gbest, gbest_fit)\n",
    "        velocity = get_velocity(pop, velocity, pbest, gbest, omega, c1, c2)\n",
    "        pop += velocity\n",
    "        pop_list.append(pop.copy())\n",
    "\n",
    "    return gbest, gbest_fit, pop_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "c68a4b34",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_fitn_demo(pop):\n",
    "    \"\"\"获取适应度\n",
    "\n",
    "    Args:\n",
    "        pop (numpy.ndarray): 粒子群，二维数组，[pn, dim]\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 适应度，一维数组，[pn]\n",
    "    \"\"\"\n",
    "    x = pop[:, 0]\n",
    "    y = pop[:, 1]\n",
    "    return np.sin(np.sqrt(x**2 + y**2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "29c67af8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "51d206eb351b4a1f9bd4c6c39180d525",
       "version_major": 2,
       "version_minor": 0
      },
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAoAAAAHgCAYAAAA10dzkAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/H5lhTAAAACXBIWXMAAA9hAAAPYQGoP6dpAAAevklEQVR4nO3df2zfdZ3A8Vfb0W8h0jJvrvtxX9yBh6jAhhurBRfCpWcTyLz9cbEHZpsLgugk3JpTNn6sIrpOBLJEigsTDpOT25QAZ1xTDnsuBqlZ3NYEZYPgwO2MLdvp2jm0Ze3n/rjw9eo6XEf3/Y7v+/FIvn/0zeez7+vLm/J95vP9sYosy7IAACAZlaUeAACA4hKAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiSmbAPzxj38cixcvjlmzZkVFRUU89dRTf/Gcbdu2xYc//OHI5XLxvve9Lx599NFTPicAQKmVTQAeOXIk5s6dGx0dHSd0/CuvvBLXXHNNXHXVVdHb2xv//M//HJ/+9Kfj6aefPsWTAgCUVkWWZVmph5hsFRUV8eSTT8aSJUuOe8ytt94aW7dujZ///OeFtX/6p3+KQ4cORVdXVxGmBAAojbK5AjhRPT090dTUNGatubk5enp6SjQRAEBxTCn1AKXS19cX9fX1Y9bq6+tjcHAw/vCHP8SZZ555zDlDQ0MxNDRU+Hl0dDR++9vfxl/91V9FRUXFKZ8ZAHj7siyLw4cPx6xZs6KyMs1rYckG4Mlob2+Pu+66q9RjAACTYP/+/fHXf/3XpR6jJJINwBkzZkR/f/+Ytf7+/qitrR336l9ExJo1a6K1tbXw88DAQJx77rmxf//+qK2tPaXzAgCTY3BwMPL5fJx99tmlHqVkkg3AxsbG6OzsHLP2zDPPRGNj43HPyeVykcvljlmvra0VgADwDpPy27fK5oXv3//+99Hb2xu9vb0R8X9f89Lb2xv79u2LiP+7erds2bLC8TfddFPs3bs3vvjFL8aePXviwQcfjO9+97uxatWqUowPAFA0ZROAP/vZz+LSSy+NSy+9NCIiWltb49JLL421a9dGRMRvfvObQgxGRPzN3/xNbN26NZ555pmYO3du3HffffGtb30rmpubSzI/AECxlOX3ABbL4OBg1NXVxcDAgJeAAeAdwvN3GV0BBADgxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMSUVQB2dHTEnDlzoqamJhoaGmL79u1vefyGDRvi/e9/f5x55pmRz+dj1apV8cc//rFI0wIAlEbZBOCWLVuitbU12traYufOnTF37txobm6O1157bdzjH3vssVi9enW0tbXF7t274+GHH44tW7bEbbfdVuTJAQCKq2wC8P77748bbrghVqxYER/84Adj48aNcdZZZ8Ujjzwy7vHPPfdcXHHFFXHdddfFnDlz4mMf+1hce+21f/GqIQDAO11ZBODw8HDs2LEjmpqaCmuVlZXR1NQUPT09455z+eWXx44dOwrBt3fv3ujs7Iyrr766KDMDAJTKlFIPMBkOHjwYIyMjUV9fP2a9vr4+9uzZM+451113XRw8eDA++tGPRpZlcfTo0bjpppve8iXgoaGhGBoaKvw8ODg4OQ8AAKCIyuIK4MnYtm1brFu3Lh588MHYuXNnPPHEE7F169a4++67j3tOe3t71NXVFW75fL6IEwMATI6KLMuyUg/xdg0PD8dZZ50Vjz/+eCxZsqSwvnz58jh06FD8x3/8xzHnLFq0KD7ykY/E17/+9cLav/3bv8WNN94Yv//976Oy8tg2Hu8KYD6fj4GBgaitrZ3cBwUAnBKDg4NRV1eX9PN3WVwBrK6ujvnz50d3d3dhbXR0NLq7u6OxsXHcc15//fVjIq+qqioiIo7XxLlcLmpra8fcAADeacriPYAREa2trbF8+fJYsGBBLFy4MDZs2BBHjhyJFStWRETEsmXLYvbs2dHe3h4REYsXL477778/Lr300mhoaIiXX3457rzzzli8eHEhBAEAylHZBGBLS0scOHAg1q5dG319fTFv3rzo6uoqfDBk3759Y6743XHHHVFRURF33HFH/PrXv473vOc9sXjx4vjqV79aqocAAFAUZfEewFLxHgIAeOfx/F0m7wEEAODECUAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxJRVAHZ0dMScOXOipqYmGhoaYvv27W95/KFDh2LlypUxc+bMyOVyccEFF0RnZ2eRpgUAKI0ppR5gsmzZsiVaW1tj48aN0dDQEBs2bIjm5uZ48cUXY/r06cccPzw8HH//938f06dPj8cffzxmz54dv/rVr+Kcc84p/vAAAEVUkWVZVuohJkNDQ0Ncdtll8cADD0RExOjoaOTz+bj55ptj9erVxxy/cePG+PrXvx579uyJM84446Tuc3BwMOrq6mJgYCBqa2vf1vwAQHF4/i6Tl4CHh4djx44d0dTUVFirrKyMpqam6OnpGfec73//+9HY2BgrV66M+vr6uOiii2LdunUxMjJy3PsZGhqKwcHBMTcAgHeasgjAgwcPxsjISNTX149Zr6+vj76+vnHP2bt3bzz++OMxMjISnZ2dceedd8Z9990XX/nKV457P+3t7VFXV1e45fP5SX0cAADFUBYBeDJGR0dj+vTp8dBDD8X8+fOjpaUlbr/99ti4ceNxz1mzZk0MDAwUbvv37y/ixAAAk6MsPgQybdq0qKqqiv7+/jHr/f39MWPGjHHPmTlzZpxxxhlRVVVVWPvABz4QfX19MTw8HNXV1ceck8vlIpfLTe7wAABFVhZXAKurq2P+/PnR3d1dWBsdHY3u7u5obGwc95wrrrgiXn755RgdHS2svfTSSzFz5sxx4w8AoFyURQBGRLS2tsamTZvi29/+duzevTs++9nPxpEjR2LFihUREbFs2bJYs2ZN4fjPfvaz8dvf/jZuueWWeOmll2Lr1q2xbt26WLlyZakeAgBAUZTFS8ARES0tLXHgwIFYu3Zt9PX1xbx586Krq6vwwZB9+/ZFZeWfejefz8fTTz8dq1atiksuuSRmz54dt9xyS9x6662leggAAEVRNt8DWAq+RwgA3nk8f5fRS8AAAJwYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQmLIKwI6OjpgzZ07U1NREQ0NDbN++/YTO27x5c1RUVMSSJUtO7YAAAKeBsgnALVu2RGtra7S1tcXOnTtj7ty50dzcHK+99tpbnvfqq6/Gv/zLv8SiRYuKNCkAQGmVTQDef//9ccMNN8SKFSvigx/8YGzcuDHOOuuseOSRR457zsjISHzyk5+Mu+66K84777wiTgsAUDplEYDDw8OxY8eOaGpqKqxVVlZGU1NT9PT0HPe8L3/5yzF9+vS4/vrrT+h+hoaGYnBwcMwNAOCdpiwC8ODBgzEyMhL19fVj1uvr66Ovr2/cc5599tl4+OGHY9OmTSd8P+3t7VFXV1e45fP5tzU3AEAplEUATtThw4dj6dKlsWnTppg2bdoJn7dmzZoYGBgo3Pbv338KpwQAODWmlHqAyTBt2rSoqqqK/v7+Mev9/f0xY8aMY47/5S9/Ga+++mosXry4sDY6OhoREVOmTIkXX3wxzj///GPOy+VykcvlJnl6AIDiKosrgNXV1TF//vzo7u4urI2OjkZ3d3c0NjYec/yFF14Yzz//fPT29hZuH//4x+Oqq66K3t5eL+0CAGWtLK4ARkS0trbG8uXLY8GCBbFw4cLYsGFDHDlyJFasWBEREcuWLYvZs2dHe3t71NTUxEUXXTTm/HPOOSci4ph1AIByUzYB2NLSEgcOHIi1a9dGX19fzJs3L7q6ugofDNm3b19UVpbFBU8AgLelIsuyrNRDvFMNDg5GXV1dDAwMRG1tbanHAQBOgOfvMnkPIAAAJ04AAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACSmrAKwo6Mj5syZEzU1NdHQ0BDbt28/7rGbNm2KRYsWxdSpU2Pq1KnR1NT0lscDAJSLsgnALVu2RGtra7S1tcXOnTtj7ty50dzcHK+99tq4x2/bti2uvfba+NGPfhQ9PT2Rz+fjYx/7WPz6178u8uQAAMVVkWVZVuohJkNDQ0Ncdtll8cADD0RExOjoaOTz+bj55ptj9erVf/H8kZGRmDp1ajzwwAOxbNmyE7rPwcHBqKuri4GBgaitrX1b8wMAxeH5u0yuAA4PD8eOHTuiqampsFZZWRlNTU3R09NzQn/G66+/Hm+88Ua8+93vPu4xQ0NDMTg4OOYGAPBOUxYBePDgwRgZGYn6+vox6/X19dHX13dCf8att94as2bNGhORf669vT3q6uoKt3w+/7bmBgAohbIIwLdr/fr1sXnz5njyySejpqbmuMetWbMmBgYGCrf9+/cXcUoAgMkxpdQDTIZp06ZFVVVV9Pf3j1nv7++PGTNmvOW59957b6xfvz5++MMfxiWXXPKWx+Zyucjlcm97XgCAUiqLK4DV1dUxf/786O7uLqyNjo5Gd3d3NDY2Hve8e+65J+6+++7o6uqKBQsWFGNUAICSK4srgBERra2tsXz58liwYEEsXLgwNmzYEEeOHIkVK1ZERMSyZcti9uzZ0d7eHhERX/va12Lt2rXx2GOPxZw5cwrvFXzXu94V73rXu0r2OAAATrWyCcCWlpY4cOBArF27Nvr6+mLevHnR1dVV+GDIvn37orLyTxc8v/nNb8bw8HD84z/+45g/p62tLb70pS8Vc3QAgKIqm+8BLAXfIwQA7zyev8vkPYAAAJw4AQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQmLIKwI6OjpgzZ07U1NREQ0NDbN++/S2P/973vhcXXnhh1NTUxMUXXxydnZ1FmhQAoHTKJgC3bNkSra2t0dbWFjt37oy5c+dGc3NzvPbaa+Me/9xzz8W1114b119/fezatSuWLFkSS5YsiZ///OdFnhwAoLgqsizLSj3EZGhoaIjLLrssHnjggYiIGB0djXw+HzfffHOsXr36mONbWlriyJEj8YMf/KCw9pGPfCTmzZsXGzduPKH7HBwcjLq6uhgYGIja2trJeSAAwCnl+TtiSqkHmAzDw8OxY8eOWLNmTWGtsrIympqaoqenZ9xzenp6orW1dcxac3NzPPXUU8e9n6GhoRgaGir8PDAwEBH/9x8SAPDO8ObzdplcAzspZRGABw8ejJGRkaivrx+zXl9fH3v27Bn3nL6+vnGP7+vrO+79tLe3x1133XXMej6fP4mpAYBS+p//+Z+oq6sr9RglURYBWCxr1qwZc9Xw0KFD8d73vjf27duX7H9Ap4vBwcHI5/Oxf//+ZC/nny7sxenFfpw+7MXpY2BgIM4999x497vfXepRSqYsAnDatGlRVVUV/f39Y9b7+/tjxowZ454zY8aMCR0fEZHL5SKXyx2zXldX55f5NFFbW2svThP24vRiP04f9uL0UVlZNp+FnbCyeOTV1dUxf/786O7uLqyNjo5Gd3d3NDY2jntOY2PjmOMjIp555pnjHg8AUC7K4gpgRERra2ssX748FixYEAsXLowNGzbEkSNHYsWKFRERsWzZspg9e3a0t7dHRMQtt9wSV155Zdx3331xzTXXxObNm+NnP/tZPPTQQ6V8GAAAp1zZBGBLS0scOHAg1q5dG319fTFv3rzo6uoqfNBj3759Yy71Xn755fHYY4/FHXfcEbfddlv87d/+bTz11FNx0UUXnfB95nK5aGtrG/dlYYrLXpw+7MXpxX6cPuzF6cNelNH3AAIAcGLK4j2AAACcOAEIAJAYAQgAkBgBCACQGAH4F3R0dMScOXOipqYmGhoaYvv27W95/Pe+97248MILo6amJi6++OLo7Ows0qTlbyJ7sWnTpli0aFFMnTo1pk6dGk1NTX9x7zhxE/29eNPmzZujoqIilixZcmoHTMhE9+LQoUOxcuXKmDlzZuRyubjgggv8f2oSTXQ/NmzYEO9///vjzDPPjHw+H6tWrYo//vGPRZq2fP34xz+OxYsXx6xZs6KioiKeeuqpv3jOtm3b4sMf/nDkcrl43/veF48++ugpn7OkMo5r8+bNWXV1dfbII49kv/jFL7IbbrghO+ecc7L+/v5xj//JT36SVVVVZffcc0/2wgsvZHfccUd2xhlnZM8//3yRJy8/E92L6667Luvo6Mh27dqV7d69O/vUpz6V1dXVZf/93/9d5MnLz0T34k2vvPJKNnv27GzRokXZP/zDPxRn2DI30b0YGhrKFixYkF199dXZs88+m73yyivZtm3bst7e3iJPXp4muh/f+c53slwul33nO9/JXnnllezpp5/OZs6cma1atarIk5efzs7O7Pbbb8+eeOKJLCKyJ5988i2P37t3b3bWWWdlra2t2QsvvJB94xvfyKqqqrKurq7iDFwCAvAtLFy4MFu5cmXh55GRkWzWrFlZe3v7uMd/4hOfyK655poxaw0NDdlnPvOZUzpnCia6F3/u6NGj2dlnn519+9vfPlUjJuNk9uLo0aPZ5Zdfnn3rW9/Kli9fLgAnyUT34pvf/GZ23nnnZcPDw8UaMSkT3Y+VK1dmf/d3fzdmrbW1NbviiitO6ZypOZEA/OIXv5h96EMfGrPW0tKSNTc3n8LJSstLwMcxPDwcO3bsiKampsJaZWVlNDU1RU9Pz7jn9PT0jDk+IqK5ufm4x3NiTmYv/tzrr78eb7zxRtJ/8fdkONm9+PKXvxzTp0+P66+/vhhjJuFk9uL73/9+NDY2xsqVK6O+vj4uuuiiWLduXYyMjBRr7LJ1Mvtx+eWXx44dOwovE+/duzc6Ozvj6quvLsrM/EmKz99l8zeBTLaDBw/GyMhI4W8SeVN9fX3s2bNn3HP6+vrGPb6vr++UzZmCk9mLP3frrbfGrFmzjvkFZ2JOZi+effbZePjhh6O3t7cIE6bjZPZi79698V//9V/xyU9+Mjo7O+Pll1+Oz33uc/HGG29EW1tbMcYuWyezH9ddd10cPHgwPvrRj0aWZXH06NG46aab4rbbbivGyPw/x3v+HhwcjD/84Q9x5plnlmiyU8cVQMre+vXrY/PmzfHkk09GTU1NqcdJyuHDh2Pp0qWxadOmmDZtWqnHSd7o6GhMnz49HnrooZg/f360tLTE7bffHhs3biz1aEnatm1brFu3Lh588MHYuXNnPPHEE7F169a4++67Sz0aCXAF8DimTZsWVVVV0d/fP2a9v78/ZsyYMe45M2bMmNDxnJiT2Ys33XvvvbF+/fr44Q9/GJdccsmpHDMJE92LX/7yl/Hqq6/G4sWLC2ujo6MRETFlypR48cUX4/zzzz+1Q5epk/m9mDlzZpxxxhlRVVVVWPvABz4QfX19MTw8HNXV1ad05nJ2Mvtx5513xtKlS+PTn/50RERcfPHFceTIkbjxxhvj9ttvH/P313NqHe/5u7a2tiyv/kW4Anhc1dXVMX/+/Oju7i6sjY6ORnd3dzQ2No57TmNj45jjIyKeeeaZ4x7PiTmZvYiIuOeee+Luu++Orq6uWLBgQTFGLXsT3YsLL7wwnn/++ejt7S3cPv7xj8dVV10Vvb29kc/nizl+WTmZ34srrrgiXn755UKER0S89NJLMXPmTPH3Np3Mfrz++uvHRN6bcZ5l2akblmMk+fxd6k+hnM42b96c5XK57NFHH81eeOGF7MYbb8zOOeecrK+vL8uyLFu6dGm2evXqwvE/+clPsilTpmT33ntvtnv37qytrc3XwEySie7F+vXrs+rq6uzxxx/PfvOb3xRuhw8fLtVDKBsT3Ys/51PAk2eie7Fv377s7LPPzj7/+c9nL774YvaDH/wgmz59evaVr3ylVA+hrEx0P9ra2rKzzz47+/d///ds79692X/+539m559/fvaJT3yiVA+hbBw+fDjbtWtXtmvXriwisvvvvz/btWtX9qtf/SrLsixbvXp1tnTp0sLxb34NzBe+8IVs9+7dWUdHh6+BSd03vvGN7Nxzz82qq6uzhQsXZj/96U8L/+zKK6/Mli9fPub47373u9kFF1yQVVdXZx/60IeyrVu3Fnni8jWRvXjve9+bRcQxt7a2tuIPXoYm+nvx/wnAyTXRvXjuueeyhoaGLJfLZeedd1721a9+NTt69GiRpy5fE9mPN954I/vSl76UnX/++VlNTU2Wz+ezz33uc9nvfve74g9eZn70ox+N+xzw5r//5cuXZ1deeeUx58ybNy+rrq7OzjvvvOxf//Vfiz53MVVkmevMAAAp8R5AAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDE/C9EV9qKDRIt0wAAAABJRU5ErkJggg==",
      "text/html": [
       "\n",
       "            <div style=\"display: inline-block;\">\n",
       "                <div class=\"jupyter-widgets widget-label\" style=\"text-align: center;\">\n",
       "                    Figure\n",
       "                </div>\n",
       "                <img src='' width=640.0/>\n",
       "            </div>\n",
       "        "
      ],
      "text/plain": [
       "Canvas(toolbar=Toolbar(toolitems=[('Home', 'Reset original view', 'home', 'home'), ('Back', 'Back to previous …"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "_, _, pop_list = pso(\n",
    "    20,\n",
    "    2,\n",
    "    0.1,\n",
    "    0.2,\n",
    "    0.2,\n",
    "    100,\n",
    "    get_decoder(np.array([-1, 1])),\n",
    "    get_fitn_demo,\n",
    ")\n",
    "PlotPSO2D()(pop_list, get_decoder(np.array([-1, 1])), get_fitn_demo)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9eb7a30c",
   "metadata": {},
   "source": [
    "#### 4.2 PSO求解极值\n",
    "\n",
    "$\\min{f(x,y)=x^2+y^2+25(\\sin(x)^2+\\sin(y)^2)}$\n",
    "\n",
    "其中：\n",
    "\n",
    "$-5\\le x,y \\le 5$\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "6c7d696e-ca45-4bb6-bd98-a5f0f3e2e422",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 答案\n",
    "def get_fitn(pop):\n",
    "    x = pop[:, 0]\n",
    "    y = pop[:, 1]\n",
    "    return x**2 + y**2 + 25 * (np.sin(x) ** 2 + np.sin(y) ** 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "02a5e3a2-da8a-4878-b890-b19bc45f5a92",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "63e4268942a8476cb003ddbd5d9cc5f0",
       "version_major": 2,
       "version_minor": 0
      },
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAoAAAAHgCAYAAAA10dzkAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/H5lhTAAAACXBIWXMAAA9hAAAPYQGoP6dpAAAevklEQVR4nO3df2zfdZ3A8Vfb0W8h0jJvrvtxX9yBh6jAhhurBRfCpWcTyLz9cbEHZpsLgugk3JpTNn6sIrpOBLJEigsTDpOT25QAZ1xTDnsuBqlZ3NYEZYPgwO2MLdvp2jm0Ze3n/rjw9eo6XEf3/Y7v+/FIvn/0zeez7+vLm/J95vP9sYosy7IAACAZlaUeAACA4hKAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiSmbAPzxj38cixcvjlmzZkVFRUU89dRTf/Gcbdu2xYc//OHI5XLxvve9Lx599NFTPicAQKmVTQAeOXIk5s6dGx0dHSd0/CuvvBLXXHNNXHXVVdHb2xv//M//HJ/+9Kfj6aefPsWTAgCUVkWWZVmph5hsFRUV8eSTT8aSJUuOe8ytt94aW7dujZ///OeFtX/6p3+KQ4cORVdXVxGmBAAojbK5AjhRPT090dTUNGatubk5enp6SjQRAEBxTCn1AKXS19cX9fX1Y9bq6+tjcHAw/vCHP8SZZ555zDlDQ0MxNDRU+Hl0dDR++9vfxl/91V9FRUXFKZ8ZAHj7siyLw4cPx6xZs6KyMs1rYckG4Mlob2+Pu+66q9RjAACTYP/+/fHXf/3XpR6jJJINwBkzZkR/f/+Ytf7+/qitrR336l9ExJo1a6K1tbXw88DAQJx77rmxf//+qK2tPaXzAgCTY3BwMPL5fJx99tmlHqVkkg3AxsbG6OzsHLP2zDPPRGNj43HPyeVykcvljlmvra0VgADwDpPy27fK5oXv3//+99Hb2xu9vb0R8X9f89Lb2xv79u2LiP+7erds2bLC8TfddFPs3bs3vvjFL8aePXviwQcfjO9+97uxatWqUowPAFA0ZROAP/vZz+LSSy+NSy+9NCIiWltb49JLL421a9dGRMRvfvObQgxGRPzN3/xNbN26NZ555pmYO3du3HffffGtb30rmpubSzI/AECxlOX3ABbL4OBg1NXVxcDAgJeAAeAdwvN3GV0BBADgxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMSUVQB2dHTEnDlzoqamJhoaGmL79u1vefyGDRvi/e9/f5x55pmRz+dj1apV8cc//rFI0wIAlEbZBOCWLVuitbU12traYufOnTF37txobm6O1157bdzjH3vssVi9enW0tbXF7t274+GHH44tW7bEbbfdVuTJAQCKq2wC8P77748bbrghVqxYER/84Adj48aNcdZZZ8Ujjzwy7vHPPfdcXHHFFXHdddfFnDlz4mMf+1hce+21f/GqIQDAO11ZBODw8HDs2LEjmpqaCmuVlZXR1NQUPT09455z+eWXx44dOwrBt3fv3ujs7Iyrr766KDMDAJTKlFIPMBkOHjwYIyMjUV9fP2a9vr4+9uzZM+451113XRw8eDA++tGPRpZlcfTo0bjpppve8iXgoaGhGBoaKvw8ODg4OQ8AAKCIyuIK4MnYtm1brFu3Lh588MHYuXNnPPHEE7F169a4++67j3tOe3t71NXVFW75fL6IEwMATI6KLMuyUg/xdg0PD8dZZ50Vjz/+eCxZsqSwvnz58jh06FD8x3/8xzHnLFq0KD7ykY/E17/+9cLav/3bv8WNN94Yv//976Oy8tg2Hu8KYD6fj4GBgaitrZ3cBwUAnBKDg4NRV1eX9PN3WVwBrK6ujvnz50d3d3dhbXR0NLq7u6OxsXHcc15//fVjIq+qqioiIo7XxLlcLmpra8fcAADeacriPYAREa2trbF8+fJYsGBBLFy4MDZs2BBHjhyJFStWRETEsmXLYvbs2dHe3h4REYsXL477778/Lr300mhoaIiXX3457rzzzli8eHEhBAEAylHZBGBLS0scOHAg1q5dG319fTFv3rzo6uoqfDBk3759Y6743XHHHVFRURF33HFH/PrXv473vOc9sXjx4vjqV79aqocAAFAUZfEewFLxHgIAeOfx/F0m7wEEAODECUAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxJRVAHZ0dMScOXOipqYmGhoaYvv27W95/KFDh2LlypUxc+bMyOVyccEFF0RnZ2eRpgUAKI0ppR5gsmzZsiVaW1tj48aN0dDQEBs2bIjm5uZ48cUXY/r06cccPzw8HH//938f06dPj8cffzxmz54dv/rVr+Kcc84p/vAAAEVUkWVZVuohJkNDQ0Ncdtll8cADD0RExOjoaOTz+bj55ptj9erVxxy/cePG+PrXvx579uyJM84446Tuc3BwMOrq6mJgYCBqa2vf1vwAQHF4/i6Tl4CHh4djx44d0dTUVFirrKyMpqam6OnpGfec73//+9HY2BgrV66M+vr6uOiii2LdunUxMjJy3PsZGhqKwcHBMTcAgHeasgjAgwcPxsjISNTX149Zr6+vj76+vnHP2bt3bzz++OMxMjISnZ2dceedd8Z9990XX/nKV457P+3t7VFXV1e45fP5SX0cAADFUBYBeDJGR0dj+vTp8dBDD8X8+fOjpaUlbr/99ti4ceNxz1mzZk0MDAwUbvv37y/ixAAAk6MsPgQybdq0qKqqiv7+/jHr/f39MWPGjHHPmTlzZpxxxhlRVVVVWPvABz4QfX19MTw8HNXV1ceck8vlIpfLTe7wAABFVhZXAKurq2P+/PnR3d1dWBsdHY3u7u5obGwc95wrrrgiXn755RgdHS2svfTSSzFz5sxx4w8AoFyURQBGRLS2tsamTZvi29/+duzevTs++9nPxpEjR2LFihUREbFs2bJYs2ZN4fjPfvaz8dvf/jZuueWWeOmll2Lr1q2xbt26WLlyZakeAgBAUZTFS8ARES0tLXHgwIFYu3Zt9PX1xbx586Krq6vwwZB9+/ZFZeWfejefz8fTTz8dq1atiksuuSRmz54dt9xyS9x6662leggAAEVRNt8DWAq+RwgA3nk8f5fRS8AAAJwYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQmLIKwI6OjpgzZ07U1NREQ0NDbN++/YTO27x5c1RUVMSSJUtO7YAAAKeBsgnALVu2RGtra7S1tcXOnTtj7ty50dzcHK+99tpbnvfqq6/Gv/zLv8SiRYuKNCkAQGmVTQDef//9ccMNN8SKFSvigx/8YGzcuDHOOuuseOSRR457zsjISHzyk5+Mu+66K84777wiTgsAUDplEYDDw8OxY8eOaGpqKqxVVlZGU1NT9PT0HPe8L3/5yzF9+vS4/vrrT+h+hoaGYnBwcMwNAOCdpiwC8ODBgzEyMhL19fVj1uvr66Ovr2/cc5599tl4+OGHY9OmTSd8P+3t7VFXV1e45fP5tzU3AEAplEUATtThw4dj6dKlsWnTppg2bdoJn7dmzZoYGBgo3Pbv338KpwQAODWmlHqAyTBt2rSoqqqK/v7+Mev9/f0xY8aMY47/5S9/Ga+++mosXry4sDY6OhoREVOmTIkXX3wxzj///GPOy+VykcvlJnl6AIDiKosrgNXV1TF//vzo7u4urI2OjkZ3d3c0NjYec/yFF14Yzz//fPT29hZuH//4x+Oqq66K3t5eL+0CAGWtLK4ARkS0trbG8uXLY8GCBbFw4cLYsGFDHDlyJFasWBEREcuWLYvZs2dHe3t71NTUxEUXXTTm/HPOOSci4ph1AIByUzYB2NLSEgcOHIi1a9dGX19fzJs3L7q6ugofDNm3b19UVpbFBU8AgLelIsuyrNRDvFMNDg5GXV1dDAwMRG1tbanHAQBOgOfvMnkPIAAAJ04AAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACSmrAKwo6Mj5syZEzU1NdHQ0BDbt28/7rGbNm2KRYsWxdSpU2Pq1KnR1NT0lscDAJSLsgnALVu2RGtra7S1tcXOnTtj7ty50dzcHK+99tq4x2/bti2uvfba+NGPfhQ9PT2Rz+fjYx/7WPz6178u8uQAAMVVkWVZVuohJkNDQ0Ncdtll8cADD0RExOjoaOTz+bj55ptj9erVf/H8kZGRmDp1ajzwwAOxbNmyE7rPwcHBqKuri4GBgaitrX1b8wMAxeH5u0yuAA4PD8eOHTuiqampsFZZWRlNTU3R09NzQn/G66+/Hm+88Ua8+93vPu4xQ0NDMTg4OOYGAPBOUxYBePDgwRgZGYn6+vox6/X19dHX13dCf8att94as2bNGhORf669vT3q6uoKt3w+/7bmBgAohbIIwLdr/fr1sXnz5njyySejpqbmuMetWbMmBgYGCrf9+/cXcUoAgMkxpdQDTIZp06ZFVVVV9Pf3j1nv7++PGTNmvOW59957b6xfvz5++MMfxiWXXPKWx+Zyucjlcm97XgCAUiqLK4DV1dUxf/786O7uLqyNjo5Gd3d3NDY2Hve8e+65J+6+++7o6uqKBQsWFGNUAICSK4srgBERra2tsXz58liwYEEsXLgwNmzYEEeOHIkVK1ZERMSyZcti9uzZ0d7eHhERX/va12Lt2rXx2GOPxZw5cwrvFXzXu94V73rXu0r2OAAATrWyCcCWlpY4cOBArF27Nvr6+mLevHnR1dVV+GDIvn37orLyTxc8v/nNb8bw8HD84z/+45g/p62tLb70pS8Vc3QAgKIqm+8BLAXfIwQA7zyev8vkPYAAAJw4AQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQmLIKwI6OjpgzZ07U1NREQ0NDbN++/S2P/973vhcXXnhh1NTUxMUXXxydnZ1FmhQAoHTKJgC3bNkSra2t0dbWFjt37oy5c+dGc3NzvPbaa+Me/9xzz8W1114b119/fezatSuWLFkSS5YsiZ///OdFnhwAoLgqsizLSj3EZGhoaIjLLrssHnjggYiIGB0djXw+HzfffHOsXr36mONbWlriyJEj8YMf/KCw9pGPfCTmzZsXGzduPKH7HBwcjLq6uhgYGIja2trJeSAAwCnl+TtiSqkHmAzDw8OxY8eOWLNmTWGtsrIympqaoqenZ9xzenp6orW1dcxac3NzPPXUU8e9n6GhoRgaGir8PDAwEBH/9x8SAPDO8ObzdplcAzspZRGABw8ejJGRkaivrx+zXl9fH3v27Bn3nL6+vnGP7+vrO+79tLe3x1133XXMej6fP4mpAYBS+p//+Z+oq6sr9RglURYBWCxr1qwZc9Xw0KFD8d73vjf27duX7H9Ap4vBwcHI5/Oxf//+ZC/nny7sxenFfpw+7MXpY2BgIM4999x497vfXepRSqYsAnDatGlRVVUV/f39Y9b7+/tjxowZ454zY8aMCR0fEZHL5SKXyx2zXldX55f5NFFbW2svThP24vRiP04f9uL0UVlZNp+FnbCyeOTV1dUxf/786O7uLqyNjo5Gd3d3NDY2jntOY2PjmOMjIp555pnjHg8AUC7K4gpgRERra2ssX748FixYEAsXLowNGzbEkSNHYsWKFRERsWzZspg9e3a0t7dHRMQtt9wSV155Zdx3331xzTXXxObNm+NnP/tZPPTQQ6V8GAAAp1zZBGBLS0scOHAg1q5dG319fTFv3rzo6uoqfNBj3759Yy71Xn755fHYY4/FHXfcEbfddlv87d/+bTz11FNx0UUXnfB95nK5aGtrG/dlYYrLXpw+7MXpxX6cPuzF6cNelNH3AAIAcGLK4j2AAACcOAEIAJAYAQgAkBgBCACQGAH4F3R0dMScOXOipqYmGhoaYvv27W95/Pe+97248MILo6amJi6++OLo7Ows0qTlbyJ7sWnTpli0aFFMnTo1pk6dGk1NTX9x7zhxE/29eNPmzZujoqIilixZcmoHTMhE9+LQoUOxcuXKmDlzZuRyubjgggv8f2oSTXQ/NmzYEO9///vjzDPPjHw+H6tWrYo//vGPRZq2fP34xz+OxYsXx6xZs6KioiKeeuqpv3jOtm3b4sMf/nDkcrl43/veF48++ugpn7OkMo5r8+bNWXV1dfbII49kv/jFL7IbbrghO+ecc7L+/v5xj//JT36SVVVVZffcc0/2wgsvZHfccUd2xhlnZM8//3yRJy8/E92L6667Luvo6Mh27dqV7d69O/vUpz6V1dXVZf/93/9d5MnLz0T34k2vvPJKNnv27GzRokXZP/zDPxRn2DI30b0YGhrKFixYkF199dXZs88+m73yyivZtm3bst7e3iJPXp4muh/f+c53slwul33nO9/JXnnllezpp5/OZs6cma1atarIk5efzs7O7Pbbb8+eeOKJLCKyJ5988i2P37t3b3bWWWdlra2t2QsvvJB94xvfyKqqqrKurq7iDFwCAvAtLFy4MFu5cmXh55GRkWzWrFlZe3v7uMd/4hOfyK655poxaw0NDdlnPvOZUzpnCia6F3/u6NGj2dlnn519+9vfPlUjJuNk9uLo0aPZ5Zdfnn3rW9/Kli9fLgAnyUT34pvf/GZ23nnnZcPDw8UaMSkT3Y+VK1dmf/d3fzdmrbW1NbviiitO6ZypOZEA/OIXv5h96EMfGrPW0tKSNTc3n8LJSstLwMcxPDwcO3bsiKampsJaZWVlNDU1RU9Pz7jn9PT0jDk+IqK5ufm4x3NiTmYv/tzrr78eb7zxRtJ/8fdkONm9+PKXvxzTp0+P66+/vhhjJuFk9uL73/9+NDY2xsqVK6O+vj4uuuiiWLduXYyMjBRr7LJ1Mvtx+eWXx44dOwovE+/duzc6Ozvj6quvLsrM/EmKz99l8zeBTLaDBw/GyMhI4W8SeVN9fX3s2bNn3HP6+vrGPb6vr++UzZmCk9mLP3frrbfGrFmzjvkFZ2JOZi+effbZePjhh6O3t7cIE6bjZPZi79698V//9V/xyU9+Mjo7O+Pll1+Oz33uc/HGG29EW1tbMcYuWyezH9ddd10cPHgwPvrRj0aWZXH06NG46aab4rbbbivGyPw/x3v+HhwcjD/84Q9x5plnlmiyU8cVQMre+vXrY/PmzfHkk09GTU1NqcdJyuHDh2Pp0qWxadOmmDZtWqnHSd7o6GhMnz49HnrooZg/f360tLTE7bffHhs3biz1aEnatm1brFu3Lh588MHYuXNnPPHEE7F169a4++67Sz0aCXAF8DimTZsWVVVV0d/fP2a9v78/ZsyYMe45M2bMmNDxnJiT2Ys33XvvvbF+/fr44Q9/GJdccsmpHDMJE92LX/7yl/Hqq6/G4sWLC2ujo6MRETFlypR48cUX4/zzzz+1Q5epk/m9mDlzZpxxxhlRVVVVWPvABz4QfX19MTw8HNXV1ad05nJ2Mvtx5513xtKlS+PTn/50RERcfPHFceTIkbjxxhvj9ttvH/P313NqHe/5u7a2tiyv/kW4Anhc1dXVMX/+/Oju7i6sjY6ORnd3dzQ2No57TmNj45jjIyKeeeaZ4x7PiTmZvYiIuOeee+Luu++Orq6uWLBgQTFGLXsT3YsLL7wwnn/++ejt7S3cPv7xj8dVV10Vvb29kc/nizl+WTmZ34srrrgiXn755UKER0S89NJLMXPmTPH3Np3Mfrz++uvHRN6bcZ5l2akblmMk+fxd6k+hnM42b96c5XK57NFHH81eeOGF7MYbb8zOOeecrK+vL8uyLFu6dGm2evXqwvE/+clPsilTpmT33ntvtnv37qytrc3XwEySie7F+vXrs+rq6uzxxx/PfvOb3xRuhw8fLtVDKBsT3Ys/51PAk2eie7Fv377s7LPPzj7/+c9nL774YvaDH/wgmz59evaVr3ylVA+hrEx0P9ra2rKzzz47+/d///ds79692X/+539m559/fvaJT3yiVA+hbBw+fDjbtWtXtmvXriwisvvvvz/btWtX9qtf/SrLsixbvXp1tnTp0sLxb34NzBe+8IVs9+7dWUdHh6+BSd03vvGN7Nxzz82qq6uzhQsXZj/96U8L/+zKK6/Mli9fPub47373u9kFF1yQVVdXZx/60IeyrVu3Fnni8jWRvXjve9+bRcQxt7a2tuIPXoYm+nvx/wnAyTXRvXjuueeyhoaGLJfLZeedd1721a9+NTt69GiRpy5fE9mPN954I/vSl76UnX/++VlNTU2Wz+ezz33uc9nvfve74g9eZn70ox+N+xzw5r//5cuXZ1deeeUx58ybNy+rrq7OzjvvvOxf//Vfiz53MVVkmevMAAAp8R5AAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDE/C9EV9qKDRIt0wAAAABJRU5ErkJggg==",
      "text/html": [
       "\n",
       "            <div style=\"display: inline-block;\">\n",
       "                <div class=\"jupyter-widgets widget-label\" style=\"text-align: center;\">\n",
       "                    Figure\n",
       "                </div>\n",
       "                <img src='' width=640.0/>\n",
       "            </div>\n",
       "        "
      ],
      "text/plain": [
       "Canvas(toolbar=Toolbar(toolitems=[('Home', 'Reset original view', 'home', 'home'), ('Back', 'Back to previous …"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "## 答案\n",
    "_, _, pop_list = pso(\n",
    "    20,\n",
    "    2,\n",
    "    0.1,\n",
    "    0.2,\n",
    "    0.2,\n",
    "    100,\n",
    "    get_decoder(np.array([-5, 5])),\n",
    "    get_fitn,\n",
    ")\n",
    "PlotPSO2D()(pop_list, get_decoder(np.array([-5, 5])), get_fitn)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef4b3bec-a3b8-4ed1-9aad-f96f6a8698bc",
   "metadata": {},
   "source": [
    "### ACO"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3e096f61-f929-4b5d-b956-8dfe225748ec",
   "metadata": {},
   "outputs": [],
   "source": [
    "#### 4.3 蚁群算法\n",
    "\n",
    "请用蚁群算法求解旅行商问题（TSP）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "7d41c46d-84e4-4449-b2fe-38f2da95fdb5",
   "metadata": {},
   "outputs": [],
   "source": [
    "class PlotTSP:\n",
    "    def __call__(self, points, paths, num):\n",
    "        self.fig, self.ax = plt.subplots(num=num)\n",
    "        self.ax.cla()\n",
    "    \n",
    "        def _update(frame):\n",
    "            idx = frame % len(paths)\n",
    "            path = paths[idx]\n",
    "            self.ax.cla()\n",
    "    \n",
    "            self.ax.set_xlim(0, 1)\n",
    "            self.ax.set_ylim(0, 1)\n",
    "            _path = np.concatenate([path, path[:, 0:1]], axis=1)\n",
    "            for i in range(path.shape[0]):\n",
    "                self.ax.plot(points[_path[i, :], 0], points[_path[i, :], 1], alpha=0.6, ls=\":\")\n",
    "            self.ax.scatter(points[:, 0], points[:, 1], c=\"r\")\n",
    "    \n",
    "        self.ani = animation.FuncAnimation(\n",
    "            self.fig, _update, frames=len(paths), interval=10, repeat=False\n",
    "        )\n",
    "        plt.show(self.ani)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "f46db1f6-e9bd-4b42-85bf-c01ad54b1b65",
   "metadata": {},
   "outputs": [],
   "source": [
    "def TSPGenerator(point_size):\n",
    "    \"\"\"生成TSP问题的点集和距离矩阵\n",
    "\n",
    "    Args:\n",
    "        point_size (int): 点的数量\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 点集，二维数组，[point_size, 2]\n",
    "        numpy.ndarray: 距离矩阵，二维数组，[point_size, point_size]\n",
    "    \"\"\"\n",
    "    points = np.random.rand(point_size, 2)\n",
    "    distance = np.zeros((point_size, point_size))\n",
    "    for i in range(point_size):\n",
    "        for j in range(point_size):\n",
    "            distance[i, j] = np.linalg.norm(points[i] - points[j])\n",
    "    return points, distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f5e1e254-a3a7-4955-b5ea-0287573bb55f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_cost(ant_path, distance):\n",
    "    \"\"\"获取蚁群路径成本\n",
    "\n",
    "    Args:\n",
    "        ant_path (numpy.ndarray): 蚁群路径，二维数组，[ant_count, point_size]\n",
    "        distance (numpy.ndarray): 距离矩阵，二维数组，[point_size, point_size]\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 蚁群路径成本，一维数组，[ant_count]\n",
    "    \"\"\"\n",
    "    ant_cost = None # 请修改\n",
    "    return ant_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "b7f7fc81-52be-4bf0-8e50-21e91cfe469b",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 答案\n",
    "def get_cost(ant_path, distance):\n",
    "    \"\"\"获取蚁群路径成本\n",
    "\n",
    "    Args:\n",
    "        ant_path (numpy.ndarray): 蚁群路径，二维数组，[ant_count, point_size]\n",
    "        distance (numpy.ndarray): 距离矩阵，二维数组，[point_size, point_size]\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 蚁群路径成本，一维数组，[ant_count]\n",
    "    \"\"\"\n",
    "    _ant_path = np.roll(ant_path, -1, axis=1)\n",
    "    ant_cost = np.sum(distance[ant_path, _ant_path], axis=1)\n",
    "    return ant_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f1f89990-5a70-4221-ba87-0a8432fad738",
   "metadata": {},
   "outputs": [],
   "source": [
    "def roulette(probabilities):\n",
    "    \"\"\"轮盘赌选择\n",
    "\n",
    "    Args:\n",
    "        probabilities (numpy.ndarray): 概率，二维数组，[ant_count, point_size]\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 选择节点idx，一维数组，[ant_count]\n",
    "    \"\"\"\n",
    "    ret = None # 请修改\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "7d42286c-8e50-4089-83d4-894cd7ba73ca",
   "metadata": {},
   "outputs": [],
   "source": [
    "def roulette(probabilities):\n",
    "    \"\"\"轮盘赌选择\n",
    "\n",
    "    Args:\n",
    "        probabilities (numpy.ndarray): 概率，二维数组，[ant_count, point_size]\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 选择节点idx，一维数组，[ant_count]\n",
    "    \"\"\"\n",
    "    ant_count, point_size = probabilities.shape\n",
    "    return np.vectorize(np.random.choice, signature=\"(n),(n)->()\")(\n",
    "        np.arange(point_size)[None, :].repeat(ant_count, axis=0),\n",
    "        p=probabilities,\n",
    "    )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d5d06fbc-09b8-40ca-ad16-e8230737be2a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_ant_paths(ant_count, point_size):\n",
    "    \"\"\"初始化蚁群路径\n",
    "\n",
    "    Args:\n",
    "        ant_count (int): 蚂蚁数量\n",
    "        point_size (int): 点的数量\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 蚁群路径，二维数组，[ant_count, point_size]\n",
    "    \"\"\"\n",
    "    ant_path = None # 请修改\n",
    "    return ant_path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "829c0b86-623b-4da0-ab5e-dcb383898b28",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 答案\n",
    "def random_ant_paths(ant_count, point_size):\n",
    "    \"\"\"初始化蚁群路径\n",
    "\n",
    "    Args:\n",
    "        ant_count (int): 蚂蚁数量\n",
    "        point_size (int): 点的数量\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 蚁群路径，二维数组，[ant_count, point_size]\n",
    "    \"\"\"\n",
    "    ant_path = np.arange(point_size)[None, :].repeat(ant_count, axis=0)\n",
    "    for i in range(ant_count):\n",
    "        np.random.shuffle(ant_path[i, :])\n",
    "    return ant_path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "00b1c3f8-0504-4609-a0e7-c477f57beda2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_ant_path(ant_path_start, tao, distance, alpha, beta):\n",
    "    \"\"\"获取蚁群路径\n",
    "\n",
    "    Args:\n",
    "        ant_path_start (numpy.ndarray): 蚁群路径起点，一维数组，[ant_count]\n",
    "        tao (numpy.ndarray): 信息素浓度，二维数组，[point_size, point_size]\n",
    "        distance (numpy.ndarray): 距离矩阵，二维数组，[point_size, point_size]\n",
    "        alpha (float): 信息度因子\n",
    "        beta (float): 启发函数因子\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 蚁群路径，二维数组，[ant_count, point_size]\n",
    "    \"\"\"\n",
    "    ant_path = None # 请修改\n",
    "    return ant_path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "70a0eaa5-f6a1-4af0-b84c-d3e86ff338e0",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 答案\n",
    "def get_ant_path(ant_path_start, tao, distance, alpha, beta):\n",
    "    \"\"\"获取蚁群路径\n",
    "\n",
    "    Args:\n",
    "        ant_path_start (numpy.ndarray): 蚁群路径起点，一维数组，[ant_count]\n",
    "        tao (numpy.ndarray): 信息素浓度，二维数组，[point_size, point_size]\n",
    "        distance (numpy.ndarray): 距离矩阵，二维数组，[point_size, point_size]\n",
    "        alpha (float): 信息度因子\n",
    "        beta (float): 启发函数因子\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 蚁群路径，二维数组，[ant_count, point_size]\n",
    "    \"\"\"\n",
    "    ant_count, point_size = ant_path_start.shape, tao.shape[0]\n",
    "    probabilities = tao**alpha * (1 / (distance + 1e-6)) ** beta\n",
    "    ant_path = ant_path_start[:, None].repeat(point_size, axis=1)\n",
    "    for i in range(1, distance.shape[0]):\n",
    "        mask = ~np.vectorize(\n",
    "            np.isin,\n",
    "            signature=\"(n),(m)->(n)\",\n",
    "            otypes=[bool],\n",
    "        )(np.arange(point_size)[None, :].repeat(ant_count, axis=0), ant_path)\n",
    "        p = np.where(mask, probabilities[ant_path[:, i - 1]] + 1e-6, 0)\n",
    "        p = p / (np.sum(p, axis=1)[:, None])\n",
    "        ant_path[:, i] = roulette(p)\n",
    "    return ant_path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "562081e2-6a55-4335-bd73-361f2b871afc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def update_tao(tao, ant_path, ant_cost, rho, Q):\n",
    "    \"\"\"更新信息素浓度\n",
    "\n",
    "    Args:\n",
    "        tao (numpy.ndarray): 上一次迭代的信息素浓度，二维数组，[point_size, point_size]\n",
    "        ant_path (numpy.ndarray): 蚁群路径，二维数组，[ant_count, point_size]\n",
    "        ant_cost (numpy.ndarray): 蚁群路径成本，一维数组，[ant_count]\n",
    "        rho (float): 信息素挥发因子\n",
    "        Q (float): 信息素增量\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 信息素浓度，二维数组，[point_size, point_size]\n",
    "    \"\"\"\n",
    "    tao = None # 请修改\n",
    "    return tao"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "69aeac14-cd4d-42c2-94a5-9facaca4a675",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 答案\n",
    "def update_tao(tao, ant_path, ant_cost, rho, Q):\n",
    "    \"\"\"更新信息素浓度\n",
    "\n",
    "    Args:\n",
    "        tao (numpy.ndarray): 上一次迭代的信息素浓度，二维数组，[point_size, point_size]\n",
    "        ant_path (numpy.ndarray): 蚁群路径，二维数组，[ant_count, point_size]\n",
    "        ant_cost (numpy.ndarray): 蚁群路径成本，一维数组，[ant_count]\n",
    "        rho (float): 信息素挥发因子\n",
    "        Q (float): 信息素增量\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: 信息素浓度，二维数组，[point_size, point_size]\n",
    "    \"\"\"\n",
    "    ant_count, point_size = ant_path.shape\n",
    "    delta_tao = np.zeros((point_size, point_size))\n",
    "    _ant_path = np.roll(ant_path, -1, axis=1)\n",
    "    delta_tao[_ant_path, ant_path] = Q / ant_cost[:, None]\n",
    "    tao = (1 - rho) * tao + delta_tao\n",
    "    return tao"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "58fe27e0-fa50-4832-9b11-9babcd35acb2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def aco(ant_count, alpha, beta, rho, Q, max_iter, distance):\n",
    "    \"\"\"蚁群算法\n",
    "\n",
    "    Args:\n",
    "        ant_count (int): 蚁群数量\n",
    "        alpha (float): 信息度因子\n",
    "        beta (float): 启发函数因子\n",
    "        rho (float): 信息素挥发因子\n",
    "        Q (float): 信息素增量\n",
    "        max_iter (int): 最大迭代次数\n",
    "        distance (numpy.ndarray): 距离矩阵，二维数组，[point_size, point_size]\n",
    "\n",
    "    Returns:\n",
    "        List: 蚁群路径迭代过程\n",
    "    \"\"\"\n",
    "    point_size = distance.shape[0]\n",
    "    tao = np.ones((point_size, point_size))\n",
    "    ant_paths = [random_ant_paths(ant_count, point_size)]\n",
    "\n",
    "    for iter in range(max_iter):\n",
    "        ant_path = ant_paths[-1]\n",
    "        ant_cost = get_cost(ant_path, distance)\n",
    "        tao = update_tao(tao, ant_path, ant_cost, rho, Q)\n",
    "        ant_paths.append(get_ant_path(ant_path[:, 0], tao, distance, alpha, beta))\n",
    "\n",
    "        if np.all(ant_paths[-1] == ant_paths[-2]):\n",
    "            break\n",
    "\n",
    "    return ant_paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8f68dacb-d509-4fa6-a68e-1a6eb774e332",
   "metadata": {},
   "outputs": [],
   "source": [
    "# points, dis = TSPGenerator(20)\n",
    "# paths = aco(...)\n",
    "# PlotTSP()(points, paths)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "6eae91d0-770e-4cca-b5d4-e617eb5ebe33",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "4e8b7764654146e3b1df54d6acb778af",
       "version_major": 2,
       "version_minor": 0
      },
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAoAAAAHgCAYAAAA10dzkAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/H5lhTAAAACXBIWXMAAA9hAAAPYQGoP6dpAAAevklEQVR4nO3df2zfdZ3A8Vfb0W8h0jJvrvtxX9yBh6jAhhurBRfCpWcTyLz9cbEHZpsLgugk3JpTNn6sIrpOBLJEigsTDpOT25QAZ1xTDnsuBqlZ3NYEZYPgwO2MLdvp2jm0Ze3n/rjw9eo6XEf3/Y7v+/FIvn/0zeez7+vLm/J95vP9sYosy7IAACAZlaUeAACA4hKAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiRGAAACJEYAAAIkRgAAAiSmbAPzxj38cixcvjlmzZkVFRUU89dRTf/Gcbdu2xYc//OHI5XLxvve9Lx599NFTPicAQKmVTQAeOXIk5s6dGx0dHSd0/CuvvBLXXHNNXHXVVdHb2xv//M//HJ/+9Kfj6aefPsWTAgCUVkWWZVmph5hsFRUV8eSTT8aSJUuOe8ytt94aW7dujZ///OeFtX/6p3+KQ4cORVdXVxGmBAAojbK5AjhRPT090dTUNGatubk5enp6SjQRAEBxTCn1AKXS19cX9fX1Y9bq6+tjcHAw/vCHP8SZZ555zDlDQ0MxNDRU+Hl0dDR++9vfxl/91V9FRUXFKZ8ZAHj7siyLw4cPx6xZs6KyMs1rYckG4Mlob2+Pu+66q9RjAACTYP/+/fHXf/3XpR6jJJINwBkzZkR/f/+Ytf7+/qitrR336l9ExJo1a6K1tbXw88DAQJx77rmxf//+qK2tPaXzAgCTY3BwMPL5fJx99tmlHqVkkg3AxsbG6OzsHLP2zDPPRGNj43HPyeVykcvljlmvra0VgADwDpPy27fK5oXv3//+99Hb2xu9vb0R8X9f89Lb2xv79u2LiP+7erds2bLC8TfddFPs3bs3vvjFL8aePXviwQcfjO9+97uxatWqUowPAFA0ZROAP/vZz+LSSy+NSy+9NCIiWltb49JLL421a9dGRMRvfvObQgxGRPzN3/xNbN26NZ555pmYO3du3HffffGtb30rmpubSzI/AECxlOX3ABbL4OBg1NXVxcDAgJeAAeAdwvN3GV0BBADgxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMSUVQB2dHTEnDlzoqamJhoaGmL79u1vefyGDRvi/e9/f5x55pmRz+dj1apV8cc//rFI0wIAlEbZBOCWLVuitbU12traYufOnTF37txobm6O1157bdzjH3vssVi9enW0tbXF7t274+GHH44tW7bEbbfdVuTJAQCKq2wC8P77748bbrghVqxYER/84Adj48aNcdZZZ8Ujjzwy7vHPPfdcXHHFFXHdddfFnDlz4mMf+1hce+21f/GqIQDAO11ZBODw8HDs2LEjmpqaCmuVlZXR1NQUPT09455z+eWXx44dOwrBt3fv3ujs7Iyrr766KDMDAJTKlFIPMBkOHjwYIyMjUV9fP2a9vr4+9uzZM+451113XRw8eDA++tGPRpZlcfTo0bjpppve8iXgoaGhGBoaKvw8ODg4OQ8AAKCIyuIK4MnYtm1brFu3Lh588MHYuXNnPPHEE7F169a4++67j3tOe3t71NXVFW75fL6IEwMATI6KLMuyUg/xdg0PD8dZZ50Vjz/+eCxZsqSwvnz58jh06FD8x3/8xzHnLFq0KD7ykY/E17/+9cLav/3bv8WNN94Yv//976Oy8tg2Hu8KYD6fj4GBgaitrZ3cBwUAnBKDg4NRV1eX9PN3WVwBrK6ujvnz50d3d3dhbXR0NLq7u6OxsXHcc15//fVjIq+qqioiIo7XxLlcLmpra8fcAADeacriPYAREa2trbF8+fJYsGBBLFy4MDZs2BBHjhyJFStWRETEsmXLYvbs2dHe3h4REYsXL477778/Lr300mhoaIiXX3457rzzzli8eHEhBAEAylHZBGBLS0scOHAg1q5dG319fTFv3rzo6uoqfDBk3759Y6743XHHHVFRURF33HFH/PrXv473vOc9sXjx4vjqV79aqocAAFAUZfEewFLxHgIAeOfx/F0m7wEEAODECUAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxJRVAHZ0dMScOXOipqYmGhoaYvv27W95/KFDh2LlypUxc+bMyOVyccEFF0RnZ2eRpgUAKI0ppR5gsmzZsiVaW1tj48aN0dDQEBs2bIjm5uZ48cUXY/r06cccPzw8HH//938f06dPj8cffzxmz54dv/rVr+Kcc84p/vAAAEVUkWVZVuohJkNDQ0Ncdtll8cADD0RExOjoaOTz+bj55ptj9erVxxy/cePG+PrXvx579uyJM84446Tuc3BwMOrq6mJgYCBqa2vf1vwAQHF4/i6Tl4CHh4djx44d0dTUVFirrKyMpqam6OnpGfec73//+9HY2BgrV66M+vr6uOiii2LdunUxMjJy3PsZGhqKwcHBMTcAgHeasgjAgwcPxsjISNTX149Zr6+vj76+vnHP2bt3bzz++OMxMjISnZ2dceedd8Z9990XX/nKV457P+3t7VFXV1e45fP5SX0cAADFUBYBeDJGR0dj+vTp8dBDD8X8+fOjpaUlbr/99ti4ceNxz1mzZk0MDAwUbvv37y/ixAAAk6MsPgQybdq0qKqqiv7+/jHr/f39MWPGjHHPmTlzZpxxxhlRVVVVWPvABz4QfX19MTw8HNXV1ceck8vlIpfLTe7wAABFVhZXAKurq2P+/PnR3d1dWBsdHY3u7u5obGwc95wrrrgiXn755RgdHS2svfTSSzFz5sxx4w8AoFyURQBGRLS2tsamTZvi29/+duzevTs++9nPxpEjR2LFihUREbFs2bJYs2ZN4fjPfvaz8dvf/jZuueWWeOmll2Lr1q2xbt26WLlyZakeAgBAUZTFS8ARES0tLXHgwIFYu3Zt9PX1xbx586Krq6vwwZB9+/ZFZeWfejefz8fTTz8dq1atiksuuSRmz54dt9xyS9x6662leggAAEVRNt8DWAq+RwgA3nk8f5fRS8AAAJwYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQmLIKwI6OjpgzZ07U1NREQ0NDbN++/YTO27x5c1RUVMSSJUtO7YAAAKeBsgnALVu2RGtra7S1tcXOnTtj7ty50dzcHK+99tpbnvfqq6/Gv/zLv8SiRYuKNCkAQGmVTQDef//9ccMNN8SKFSvigx/8YGzcuDHOOuuseOSRR457zsjISHzyk5+Mu+66K84777wiTgsAUDplEYDDw8OxY8eOaGpqKqxVVlZGU1NT9PT0HPe8L3/5yzF9+vS4/vrrT+h+hoaGYnBwcMwNAOCdpiwC8ODBgzEyMhL19fVj1uvr66Ovr2/cc5599tl4+OGHY9OmTSd8P+3t7VFXV1e45fP5tzU3AEAplEUATtThw4dj6dKlsWnTppg2bdoJn7dmzZoYGBgo3Pbv338KpwQAODWmlHqAyTBt2rSoqqqK/v7+Mev9/f0xY8aMY47/5S9/Ga+++mosXry4sDY6OhoREVOmTIkXX3wxzj///GPOy+VykcvlJnl6AIDiKosrgNXV1TF//vzo7u4urI2OjkZ3d3c0NjYec/yFF14Yzz//fPT29hZuH//4x+Oqq66K3t5eL+0CAGWtLK4ARkS0trbG8uXLY8GCBbFw4cLYsGFDHDlyJFasWBEREcuWLYvZs2dHe3t71NTUxEUXXTTm/HPOOSci4ph1AIByUzYB2NLSEgcOHIi1a9dGX19fzJs3L7q6ugofDNm3b19UVpbFBU8AgLelIsuyrNRDvFMNDg5GXV1dDAwMRG1tbanHAQBOgOfvMnkPIAAAJ04AAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACRGAAIAJEYAAgAkRgACACSmrAKwo6Mj5syZEzU1NdHQ0BDbt28/7rGbNm2KRYsWxdSpU2Pq1KnR1NT0lscDAJSLsgnALVu2RGtra7S1tcXOnTtj7ty50dzcHK+99tq4x2/bti2uvfba+NGPfhQ9PT2Rz+fjYx/7WPz6178u8uQAAMVVkWVZVuohJkNDQ0Ncdtll8cADD0RExOjoaOTz+bj55ptj9erVf/H8kZGRmDp1ajzwwAOxbNmyE7rPwcHBqKuri4GBgaitrX1b8wMAxeH5u0yuAA4PD8eOHTuiqampsFZZWRlNTU3R09NzQn/G66+/Hm+88Ua8+93vPu4xQ0NDMTg4OOYGAPBOUxYBePDgwRgZGYn6+vox6/X19dHX13dCf8att94as2bNGhORf669vT3q6uoKt3w+/7bmBgAohbIIwLdr/fr1sXnz5njyySejpqbmuMetWbMmBgYGCrf9+/cXcUoAgMkxpdQDTIZp06ZFVVVV9Pf3j1nv7++PGTNmvOW59957b6xfvz5++MMfxiWXXPKWx+Zyucjlcm97XgCAUiqLK4DV1dUxf/786O7uLqyNjo5Gd3d3NDY2Hve8e+65J+6+++7o6uqKBQsWFGNUAICSK4srgBERra2tsXz58liwYEEsXLgwNmzYEEeOHIkVK1ZERMSyZcti9uzZ0d7eHhERX/va12Lt2rXx2GOPxZw5cwrvFXzXu94V73rXu0r2OAAATrWyCcCWlpY4cOBArF27Nvr6+mLevHnR1dVV+GDIvn37orLyTxc8v/nNb8bw8HD84z/+45g/p62tLb70pS8Vc3QAgKIqm+8BLAXfIwQA7zyev8vkPYAAAJw4AQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQGAEIAJAYAQgAkBgBCACQmLIKwI6OjpgzZ07U1NREQ0NDbN++/S2P/973vhcXXnhh1NTUxMUXXxydnZ1FmhQAoHTKJgC3bNkSra2t0dbWFjt37oy5c+dGc3NzvPbaa+Me/9xzz8W1114b119/fezatSuWLFkSS5YsiZ///OdFnhwAoLgqsizLSj3EZGhoaIjLLrssHnjggYiIGB0djXw+HzfffHOsXr36mONbWlriyJEj8YMf/KCw9pGPfCTmzZsXGzduPKH7HBwcjLq6uhgYGIja2trJeSAAwCnl+TtiSqkHmAzDw8OxY8eOWLNmTWGtsrIympqaoqenZ9xzenp6orW1dcxac3NzPPXUU8e9n6GhoRgaGir8PDAwEBH/9x8SAPDO8ObzdplcAzspZRGABw8ejJGRkaivrx+zXl9fH3v27Bn3nL6+vnGP7+vrO+79tLe3x1133XXMej6fP4mpAYBS+p//+Z+oq6sr9RglURYBWCxr1qwZc9Xw0KFD8d73vjf27duX7H9Ap4vBwcHI5/Oxf//+ZC/nny7sxenFfpw+7MXpY2BgIM4999x497vfXepRSqYsAnDatGlRVVUV/f39Y9b7+/tjxowZ454zY8aMCR0fEZHL5SKXyx2zXldX55f5NFFbW2svThP24vRiP04f9uL0UVlZNp+FnbCyeOTV1dUxf/786O7uLqyNjo5Gd3d3NDY2jntOY2PjmOMjIp555pnjHg8AUC7K4gpgRERra2ssX748FixYEAsXLowNGzbEkSNHYsWKFRERsWzZspg9e3a0t7dHRMQtt9wSV155Zdx3331xzTXXxObNm+NnP/tZPPTQQ6V8GAAAp1zZBGBLS0scOHAg1q5dG319fTFv3rzo6uoqfNBj3759Yy71Xn755fHYY4/FHXfcEbfddlv87d/+bTz11FNx0UUXnfB95nK5aGtrG/dlYYrLXpw+7MXpxX6cPuzF6cNelNH3AAIAcGLK4j2AAACcOAEIAJAYAQgAkBgBCACQGAH4F3R0dMScOXOipqYmGhoaYvv27W95/Pe+97248MILo6amJi6++OLo7Ows0qTlbyJ7sWnTpli0aFFMnTo1pk6dGk1NTX9x7zhxE/29eNPmzZujoqIilixZcmoHTMhE9+LQoUOxcuXKmDlzZuRyubjgggv8f2oSTXQ/NmzYEO9///vjzDPPjHw+H6tWrYo//vGPRZq2fP34xz+OxYsXx6xZs6KioiKeeuqpv3jOtm3b4sMf/nDkcrl43/veF48++ugpn7OkMo5r8+bNWXV1dfbII49kv/jFL7IbbrghO+ecc7L+/v5xj//JT36SVVVVZffcc0/2wgsvZHfccUd2xhlnZM8//3yRJy8/E92L6667Luvo6Mh27dqV7d69O/vUpz6V1dXVZf/93/9d5MnLz0T34k2vvPJKNnv27GzRokXZP/zDPxRn2DI30b0YGhrKFixYkF199dXZs88+m73yyivZtm3bst7e3iJPXp4muh/f+c53slwul33nO9/JXnnllezpp5/OZs6cma1atarIk5efzs7O7Pbbb8+eeOKJLCKyJ5988i2P37t3b3bWWWdlra2t2QsvvJB94xvfyKqqqrKurq7iDFwCAvAtLFy4MFu5cmXh55GRkWzWrFlZe3v7uMd/4hOfyK655poxaw0NDdlnPvOZUzpnCia6F3/u6NGj2dlnn519+9vfPlUjJuNk9uLo0aPZ5Zdfnn3rW9/Kli9fLgAnyUT34pvf/GZ23nnnZcPDw8UaMSkT3Y+VK1dmf/d3fzdmrbW1NbviiitO6ZypOZEA/OIXv5h96EMfGrPW0tKSNTc3n8LJSstLwMcxPDwcO3bsiKampsJaZWVlNDU1RU9Pz7jn9PT0jDk+IqK5ufm4x3NiTmYv/tzrr78eb7zxRtJ/8fdkONm9+PKXvxzTp0+P66+/vhhjJuFk9uL73/9+NDY2xsqVK6O+vj4uuuiiWLduXYyMjBRr7LJ1Mvtx+eWXx44dOwovE+/duzc6Ozvj6quvLsrM/EmKz99l8zeBTLaDBw/GyMhI4W8SeVN9fX3s2bNn3HP6+vrGPb6vr++UzZmCk9mLP3frrbfGrFmzjvkFZ2JOZi+effbZePjhh6O3t7cIE6bjZPZi79698V//9V/xyU9+Mjo7O+Pll1+Oz33uc/HGG29EW1tbMcYuWyezH9ddd10cPHgwPvrRj0aWZXH06NG46aab4rbbbivGyPw/x3v+HhwcjD/84Q9x5plnlmiyU8cVQMre+vXrY/PmzfHkk09GTU1NqcdJyuHDh2Pp0qWxadOmmDZtWqnHSd7o6GhMnz49HnrooZg/f360tLTE7bffHhs3biz1aEnatm1brFu3Lh588MHYuXNnPPHEE7F169a4++67Sz0aCXAF8DimTZsWVVVV0d/fP2a9v78/ZsyYMe45M2bMmNDxnJiT2Ys33XvvvbF+/fr44Q9/GJdccsmpHDMJE92LX/7yl/Hqq6/G4sWLC2ujo6MRETFlypR48cUX4/zzzz+1Q5epk/m9mDlzZpxxxhlRVVVVWPvABz4QfX19MTw8HNXV1ad05nJ2Mvtx5513xtKlS+PTn/50RERcfPHFceTIkbjxxhvj9ttvH/P313NqHe/5u7a2tiyv/kW4Anhc1dXVMX/+/Oju7i6sjY6ORnd3dzQ2No57TmNj45jjIyKeeeaZ4x7PiTmZvYiIuOeee+Luu++Orq6uWLBgQTFGLXsT3YsLL7wwnn/++ejt7S3cPv7xj8dVV10Vvb29kc/nizl+WTmZ34srrrgiXn755UKER0S89NJLMXPmTPH3Np3Mfrz++uvHRN6bcZ5l2akblmMk+fxd6k+hnM42b96c5XK57NFHH81eeOGF7MYbb8zOOeecrK+vL8uyLFu6dGm2evXqwvE/+clPsilTpmT33ntvtnv37qytrc3XwEySie7F+vXrs+rq6uzxxx/PfvOb3xRuhw8fLtVDKBsT3Ys/51PAk2eie7Fv377s7LPPzj7/+c9nL774YvaDH/wgmz59evaVr3ylVA+hrEx0P9ra2rKzzz47+/d///ds79692X/+539m559/fvaJT3yiVA+hbBw+fDjbtWtXtmvXriwisvvvvz/btWtX9qtf/SrLsixbvXp1tnTp0sLxb34NzBe+8IVs9+7dWUdHh6+BSd03vvGN7Nxzz82qq6uzhQsXZj/96U8L/+zKK6/Mli9fPub47373u9kFF1yQVVdXZx/60IeyrVu3Fnni8jWRvXjve9+bRcQxt7a2tuIPXoYm+nvx/wnAyTXRvXjuueeyhoaGLJfLZeedd1721a9+NTt69GiRpy5fE9mPN954I/vSl76UnX/++VlNTU2Wz+ezz33uc9nvfve74g9eZn70ox+N+xzw5r//5cuXZ1deeeUx58ybNy+rrq7OzjvvvOxf//Vfiz53MVVkmevMAAAp8R5AAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDECEAAgMQIQACAxAhAAIDE/C9EV9qKDRIt0wAAAABJRU5ErkJggg==",
      "text/html": [
       "\n",
       "            <div style=\"display: inline-block;\">\n",
       "                <div class=\"jupyter-widgets widget-label\" style=\"text-align: center;\">\n",
       "                    1\n",
       "                </div>\n",
       "                <img src='' width=640.0/>\n",
       "            </div>\n",
       "        "
      ],
      "text/plain": [
       "Canvas(toolbar=Toolbar(toolitems=[('Home', 'Reset original view', 'home', 'home'), ('Back', 'Back to previous …"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "## 答案\n",
    "points, dis = TSPGenerator(20)\n",
    "paths = aco(8, 2, 2.5, 0.7, 1, 500, dis)\n",
    "PlotTSP()(points, paths)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "667b7649-a509-4125-b907-ff77379aa7b8",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
